#include <stdio.h>
#include <stdlib.h>


// 链表的结构体
typedef struct LinkNode{
    int data;
    struct LinkNode * next;
} * LinkList;


/**
 * 初始化链表（带头节点）
 * @param lNode
 */
void initLinkNode(LinkList lNode) {
    // 头节点默认指向NULL, 头节点不存储数据
    struct LinkNode * head = lNode;
    head->next = NULL;
}

/**
 * 链表插入操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @param data 插入的数据
 * @return 0表示失败，1表示成功
 */
_Bool insertNode(LinkList head, int index, int data) {
    // 非法位序
    if(index < 1) {
        return 0;
    }
    struct LinkNode * p = head;
    // --index 先减然后再操作
    while(--index) {
        // 当index为0时，p指向的恰好是插入位置的前一个节点
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 为插入的新节点分配内存
    LinkList newNode = malloc(sizeof(LinkList));
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return 1;
}

/**
 * 链表删除操作
 * @param head 头节点指针
 * @param index 位序（从1开始）
 * @return
 */
_Bool deleteNode(LinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    LinkList p = head;
    // 只有头节点的时候
    if(p->next == NULL) {
        return 0;
    }
    while(--index){
        p = p->next;
        // index越界
        if(p == NULL) {
            return 0;
        }
    }
    // 记录要删除的节点后再删除
    struct LinkNode * q = p->next;
    p->next = q->next;
    // 释放内存
    free(q);
    return 1;
}

/**
 * 根据位序查找元素
 */
int findNodeData(LinkList head, int index) {
    //非法位序
    if(index < 1) {
        return 0;
    }
    LinkList p = head;
    if(p->next == NULL) {
        return INT_MAX;
    }
    while (--index) {
        p = p->next;
        if(p == NULL) {
            return INT_MAX;
        }
    }
    return p->next->data;
}

/**
 * 计算链表长度（除头节点）
 */
int getLinkListLength(LinkList head) {
    int size = 0;
    while (head->next) {
        head = head->next;
        size++;
    }
    return size;
}

/**
 * 打印数据
 */
void printLinkList(LinkList linkList) {
    while (linkList) {
        linkList = linkList->next;
        printf("%d\t", linkList->data);
    }
}

int main2() {
    struct LinkNode head;
    initLinkNode(&head);
    insertNode(&head, 1, 10);
    insertNode(&head, 1, 20);
    insertNode(&head, 3, 30);
    deleteNode(&head, 1);
    printf("%d\n", findNodeData(&head, 2));
    printf("%d\n", getLinkListLength(&head));
    printLinkList(&head);
}


